# 整数数组 nums 按升序排列，数组中的值 互不相同 。 
# 
#  在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[
# k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2
# ,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 
# 
#  给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [4,5,6,7,0,1,2], target = 0
# 输出：4
#  
# 
#  示例 2： 
# 
#  
# 输入：nums = [4,5,6,7,0,1,2], target = 3
# 输出：-1 
# 
#  示例 3： 
# 
#  
# 输入：nums = [1], target = 0
# 输出：-1
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 5000 
#  -10^4 <= nums[i] <= 10^4 
#  nums 中的每个值都 独一无二 
#  题目数据保证 nums 在预先未知的某个下标上进行了旋转 
#  -10^4 <= target <= 10^4 
#  
# 
#  
# 
#  进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？ 
#  Related Topics 数组 二分查找 
#  👍 1620 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[l] <= nums[mid]:
                if nums[l] <= target <= nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 解法1: 循环判断
#     def search(self, nums: List[int], target: int) -> int:
#         for i, n in enumerate(nums):
#             if nums[i] == target:
#                 return i
#         return -1
# 解法2: 二分法搜索
# 局部有序也可以二分法搜索
# num[l] <= nums[mid]  l - mid 有序
# 判断是否落在有序序列中, 移动左右坐标
#     def search(self, nums: List[int], target: int) -> int:
#         if not nums:
#             return -1
#         l, r = 0, len(nums) - 1
#         while l <= r:
#             mid = (l + r) // 2
#             if nums[mid] == target:
#                 return mid
#             if nums[l] <= nums[mid]:
#                 if nums[l] <= target < nums[mid]:
#                     r = mid - 1
#                 else:
#                     l = mid + 1
#             else:
#                 if nums[mid] < target <= nums[r]:
#                     l = mid + 1
#                 else:
#                     r = mid - 1
#         return -1
if __name__ == '__main__':
    s = Solution()
    nums1 = [4, 5, 6, 7, 0, 1, 2]
    e1 = s.search(nums1, 0)
    assert e1 == 4, e1
    e2 = s.search(nums1, 3)
    assert e2 == -1, e2
    nums2 = [1, 3, 5]
    # l = 0 , r = 2
    # mid = 1
    #
    e3 = s.search(nums2, 1)
    assert e3 == 0, e3
    nums3 = [5, 1, 3]
    e4 = s.search(nums3, 3)
    assert e4 == 2, e4
